АА дрво

АА дрво у рачунарским наукама је форма балансираног дрвета које се користи за чување и враћање сложених података ефикасно. АА дрва се названа по Arne Andersson, њиховом проналазачу.

АА дрва су варијација црвено-црних дрва, форма бинарно претраживачког стабла које подржава ефикасно додавање и брисање улаза. За разлику од црвено-црниог дрвета, црвени чворови на АА дрвету могу једино да буду додата као десна деца. Другим речима, ниједан црвени чвор не може да буде лево дете. Ово резултује симулацији 2-3 дрвета уместо 2-3-4 дрвета, што врло поједностављује операције за одржавање. Алгоритми за одржавање у црвено-црном дрвету су захтевале узимање у обзир седам различитих облика да би се правилно балансирало дрво:

АА дрво у другу руку само треба да узме у обзир дава облика с обзиром на стриктну потребу да само десне везе могу да буду црвене:

Балансирајуће ротације

Док црвено-црно дрво захтева један део балансирајућих мета података по чвору (боју), АА дрва захтевају O(log(N)) делова мета података по чвору; у форми целог броја "нивоа". Следеће инваријанте постоје за АА дрва:

1. Ниво сваког чвора који је лист је један.
2. Ниво сваког левог детета је тачно за један мањи од родитеља.
3. Ниво сваког десног детета је једнак или мањи за један од његовог родитеља.
4. Ниво сваког десног унука је стриктно мањи од нивоа родитеља родитеља.
5. Сваки чор нивоа већег од један има двоје деце.

Веза где је ниво детета једнак родитељевом се зове хоризонтална веза, и аналогна је црвеној вези у црвено-црном дрвету. Индивидуалне десне хоризонталне везе су дозвољене, али узастопне су забрањене; све лефе хоризонталне везе су забрањене. Ово су строжа ограничења од аналогних ограничења црвено-црног дрвета, са резултатом да је ребалансирање АА дрвета процедурално много једноставније од ребалансирања црвено-црног дрвета.

Убацивања и брисања могу пролазно да изазову да АА дрво постане небалансирано (што значи, да прекрше инваријанте АА дрвета). Само две сличне операције су потребне за ребалансирање "skew" и "split". Skew је десна ротација која замењује поддрво које садржи леву хоризонталну везу са оним које садржи десну хоризонталну везу. Split је лева ротација и повећање нивоа да се замени поддрво које садржи две или више узастопних десних хоризонталних веза са оним које садржи мање узастопних десних хоризонталних веза. Имплементација убацивања и брисања који одржавају баланс је поједностављено увођењем skew и split операција за модификацију дрвета само ако је потребно, уместо прављењем њихових позива да ли да раде skew или split.

function skew is
    input: T, a node representing an AA tree that needs to be rebalanced.
    output: Another node representing the rebalanced AA tree.

    if nil(T) then
        return Nil
    else if nil(left(T)) then
        return T
    else if level(left(T)) == level(T) then
        Swap the pointers of horizontal left links.
        L = left(T)
        left(T) := right(L)
        right(L) := T
        return L
    else
        return T
    end if
end function

Skew:

function split is
    input: T, a node representing an AA tree that needs to be rebalanced.
    output: Another node representing the rebalanced AA tree.

    if nil(T) then
        return Nil
    else if nil(right(T)) or  nil(right(right(T))) then
        return T
    else if level(T) == level(right(right(T))) then
        We have two horizontal right links.  Take the middle node, elevate it, and return it.
        R = right(T)
        right(T) := left(R)
        left(R) := T
        level(R) := level(R) + 1
        return R
    else
        return T
    end if
end function

Split:

Додавање

Убацивање почиње са нормалним бинарним претраживачким дрветом и процедуром убацивања. Затим, како се стек звања развија (претпостављајући рекурзивну имплементацију претраживања), лако се проверава тачност дрвета и изводи било која ротација ако је потребно. Ако хоризонтална лева веза настане, извешће се skew, и ако две хоризонталне десне везе настану, извешће се split, могуће инкрементирајући ниво новог чвора који је корен тренутног подстабла. Приметимо, у горе датом коду, инкрементација нивоа (Т). Ово чини неопходним настављање проверавања тачности дрвета како модификације израњају из листова.

function insert is
    input: X, the value to be inserted, and T, the root of the tree to insert it into.
    output: A balanced version T including X.

    Do the normal binary tree insertion procedure. Set the result of the
    recursive call to the correct child in case a new node was created or the
    root of the subtree changes.
    if nil(T) then
        Create a new leaf node with X.
        return node(X, 1, Nil, Nil)
    else if X < value(T) then
        left(T) := insert(X, left(T))
    else if X > value(T) then
        right(T) := insert(X, right(T))
    end if
    Note that the case of X == value(T) is unspecified. As given, an insert
    will have no effect. The implementor may desire different behavior.

    Perform skew and then split. The conditionals that determine whether or
    not a rotation will occur or not are inside of the procedures, as given
    above.
    T := skew(T)
    T := split(T)

    return T
end function

Брисање

Као у већини балансираних бинарних дрвећа, брисање унутрашњег чвора може бити претворено у брисање чвора који је лист замењујући унутрашњи чвор са или најближим претком или наследником, зависно од тога који су у дрвету или имплементаторским хировима. Враћање претка је једноставно ствар праћења једне леве везе и онда свих преосталиих десних веза. Исто, наследник може да се пронађе идући једном десно и лево док се не стигне до показивача на нулу. Због карактеристике АА да сви чворови нивоа већег од један који имају двоје деце, наследник или предак ће бити у нивоу 1, што чини њихово уклањање тривијалним.

Да би се ребалансирало дрво, постоји неколико приступа. Један описан од стране Andersson у његовом оригиналном раду је најједноставнији, и описан је овде, међутим стварна имплементација може да се одлучи за оптимизованији приступ. Након уклањања, први корак за одржавање валидности дрвета је да се смањи ниво сваког чвора чија су деца два нивоа испод њих, или којима недотају деца. Онда, Цео ниво мора да се skewed и split. Овај приступ је фаворизован, јер када се прикаже концептуално, има три једноставно разумљивих одвојених корака:

1. Смањи ниво, ако је потребно.
2. Skew ниво.
3. Split ниво.

Међутим, морамо да skew и split цео ниво овај пут уместо само чвора, компликујући наш код.

function delete is
    input: X, the value to delete, and T, the root of the tree from which it should be deleted.
    output: T, balanced, without the value X.
   
    if nil(T) then
        return T
    else if X > value(T) then
        right(T) := delete(X, right(T))
    else if X < value(T) then
        left(T) := delete(X, left(T))
    else
        If we're a leaf, easy, otherwise reduce to leaf case. 
        if leaf(T) then
            return Nil
        else if nil(left(T)) then
            L := successor(T)
            right(T) := delete(value(L), right(T))
            value(T) := value(L)
        else
            L := predecessor(T)
            left(T) := delete(value(L), left(T))
            value(T) := value(L)
        end if
    end if

    Rebalance the tree. Decrease the level of all nodes in this level if
    necessary, and then skew and split all nodes in the new level.
    T := decrease_level(T)
    T := skew(T)
    right(T) := skew(right(T))
    if not nil(right(T))
        right(right(T)) := skew(right(right(T)))
    end if
    T := split(T)
    right(T) := split(right(T))
    return T
end function

function decrease_level is
    input: T, a tree for which we want to remove links that skip levels.
    output: T with its level decreased.

    should_be = min(level(left(T)), level(right(T))) + 1
    if should_be < level(T) then
        level(T) := should_be
        if should_be < level(right(T)) then
            level(right(T)) := should_be
        end if
    end if
    return T
end function

Добар пример брисања овим алгоритмом се налази у Andersson paper.

Перформансе

Перформансе АА дрвета су еквивалентне перформансама црвено-црног дрвета. Док АА дрво прави више ротација него црвено-црно дрво, једноставнији алгоритми теже да буду бржи, и све ово балансира до сличних перформанси. Црвено-црно дрво је конзистентније у пеформансама него АА дрво, али АА дрво тежи да буде равније, што резултује за нијансу бржем времену претраживања.

Види још

• Red-black tree
• B-tree
• AVL tree
• Scapegoat tree

Спољашње везе

• A. Andersson. Balanced search trees made simple
• A. Andersson. A note on searching in a binary search tree
• AA-Tree Applet Архивирано на сајту Wayback Machine (4. март 2015) by Kubo Kovac
• BSTlib Архивирано на сајту Wayback Machine (7. август 2011) - Open source AA tree library for C by trijezdci
• AA Visual 2007 1.5 - OpenSource Delphi program for educating AA tree structures
• Thorough tutorial Julienne Walker with lots of code, including a practical implementation
• Object Oriented implementation with tests
• A Disquisition on The Performance Behavior of Binary Search Tree Data Structures (pages 67-75) - Comparison of AA trees, red-black trees, treaps, skip lists, and radix trees
• An Objective-C implementation